package com.leetcode.search.backtracking;

import java.util.*;

/**
 * @author Dennis Li
 * @date 2020/7/27 16:38
 */
public class PermuteUnique_47 {

    private final List<List<Integer>> res = new ArrayList<>();
    private boolean[] visited;

    public List<List<Integer>> permuteUnique(int[] nums) {
        // 先进行排序，保证相同的数字近邻
        Arrays.sort(nums);
        // 这时通过序号是否被访问过来进行回溯 -- 类似Set，但效率更高
        visited = new boolean[nums.length];
        backtrack(nums, new LinkedList<>());
        return res;
    }

    private void backtrack(int[] nums, LinkedList<Integer> list) {
        if (nums.length == list.size()) {
            res.add(new LinkedList<>(list));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            // 直接跳过重复的节点
            // 剪枝，避免重复进入
            if (i != 0 && nums[i] == nums[i - 1] && !visited[i - 1]) continue;  // 防止重复
            if (!visited[i]) {
                // 表示序号已被访问过
                visited[i] = true;
                list.add(nums[i]);
                backtrack(nums, list);
                list.removeLast();
                visited[i] = false;
            }
        }
    }

}
